package com.liufei.class03;

import java.util.Arrays;

public class Code04_BSAwesome {
    // arr 整体无序
    // arr 相邻的数不相等！
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1) {
            return 0;
        }
        int L = 0;
        int R = arr.length - 1;
        // 这里不能直接 L <= R 。否则会越界，必须保证至少右3个数以上，才可以走下面的逻辑
        while (L < R - 1) {
            int mid = (L + R) / 2;
            // 找到了，直接返回mid即可。趋势相当于 V
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                // 相当于上升趋势是 / ，继续往左找
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else { // 下降趋势 \，继续往右找
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }


    public static boolean check(int[] arr, int oneMinIndex) {
        if (arr == null || arr.length == 0) {
            return oneMinIndex == -1;
        }
        if (arr.length == 1) {
            return oneMinIndex == 0;
        }
        boolean flag1 = oneMinIndex - 1 > 0 ? arr[oneMinIndex - 1] > arr[oneMinIndex] : true;
        boolean flag2 = oneMinIndex + 1 < arr.length ? arr[oneMinIndex] < arr[oneMinIndex + 1] : true;
        return flag1 && flag2;
    }

    // 生成随机数组，且相邻数不相等
    public static int[] randomArray(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen);
        int[] arr = new int[len];
        if (arr.length > 0) {
            arr[0] = (int) (Math.random() * maxValue);
            for (int i = 1; i < arr.length; i++) {
                do {
                    arr[i] = (int) (Math.random() * maxValue);
                } while (arr[i] == arr[i - 1]);
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int maxLen = 50;
        int maxValue = 1000;
        int times = 100000;
        System.out.println("测试开始！");
        for (int i = 0; i < times; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int oneMinIndex = oneMinIndex(arr);
            if (!check(arr, oneMinIndex)) {
                System.out.println(Arrays.toString(arr));
                System.out.println("其中一个局部最小位置：" + oneMinIndex);
                break;
            }
        }
        System.out.println("测试结束！");

//        int[] arr = {9, 4, 3, 6};
//        int oneMinIndex = oneMinIndex(arr);
//        System.out.println(oneMinIndex);
    }
}
